package com.example.leetcode;

import java.util.ArrayList;
import java.util.List;

public class Demo0120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        int size = triangle.size();
        List<List<Integer>> fun=new ArrayList<>();
        fun.add(triangle.get(0));
        for (int i = 1; i < size; i++) {
            List<Integer> list=new ArrayList(i+1);
            for (int j = 0; j < i+1; j++) {
                if (j==0){
                    list.add(triangle.get(i).get(0)+fun.get(i-1).get(0));
                    continue;
                }
                if (j==i){
                    list.add(triangle.get(i).get(j)+fun.get(i-1).get(j-1));
                    continue;
                }
                list.add(Math.min(triangle.get(i).get(j)+fun.get(i-1).get(j-1),
                        triangle.get(i).get(j)+fun.get(i-1).get(j)));
            }
            fun.add(list);
        }
        int ans=fun.get(size-1).get(0);
        for (int i = 1; i < size; i++) {
            ans=Math.min(ans, fun.get(size-1).get(i));
        }
        return ans;
    }
}
